Reed-Solomon (RS) codes are a powerful class of multiple error-correcting codes. RS codes have a wide range of applications, such as optical communications, wireless communications and magnetic recording systems. When applying systematic Reed-Solomon encoding, data is transmitted in codewords that represent a combination of the original data symbols and a number of parity symbols. An RS code that uses 2t parity symbols is commonly correctable to t errors. An RS decoder uses the 2t parity symbols to correct a received message, even if the received message experiences up to t errors during transmission.
In many modern communication systems, RS decoders use extra information along with the received data. A reliability value is calculated for each received data symbol. Received data symbols with very small reliability are called erasures. If a particular data symbol in a received codeword is known to be an erasure, a value of the particular symbol is ignored when the RS decoder attempts to decode the codeword. If ν errors and ρ erasures occur during transmission of a codeword, the codeword can be corrected if and only if ν+ρ≦2t. RS decoders that use information about erasures are called error-and-erasure decoders. The error-and-erasure decoding techniques involve the construction of erasure locator polynomials. The erasure locator polynomials accumulate information about all of the erasures for use in the decoding process.